#include "stdafx.h"
#include "Solution.h"

void Solution::merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n)
{
    // nums1 valid range [0, m)
    // nums2 valid range [0, n)

    // copy nums1[0, m) to nums1[nums1.size() - m, nums1.size())
    // we should copy from right to left to avoid overlap

    // loop invariants:
    // has copied nums1[i, m) to nums1[nums1.size() - (m - i), nums1.size())
    for (ptrdiff_t i = m; i > 0  ; --i) {
        // we are copying at index "i - 1" to "nums1.size() - (m - i) - 1"
        nums1[static_cast<ptrdiff_t>(nums1.size()) - (m - i) - 1] = nums1[i - 1];
    }
    // post condition:
    // has copied nums1[0, m) to nums1[nums1.size() - m, nums1.size())

    ptrdiff_t first1 = static_cast<ptrdiff_t>(nums1.size()) - m;
    ptrdiff_t last1 = nums1.size();
    ptrdiff_t first2 = 0;
    ptrdiff_t last2 = n;
    ptrdiff_t last3 = 0;

    // loop invariants: first1, first2, last3
    // [first1, last1) to merge
    // [first2, last2) to merge
    // [0, last3) is the merge result
    while (first1 < last1 && first2 < last2) {
        int val1 = nums1[first1];
        int val2 = nums2[first2];
        if (val1 < val2) {
            nums1[last3++] = val1;
            ++first1;
        }
        else {
            nums1[last3++] = val2;
            ++first2;
        }
    }
    // post condition: first1 == last1 or first2 == last2
    // [0, last3) is the merge result

    if (first1 == last1) {
        // we should copy nums2[first2, last2) to the result

        // loop invariant:
        // nums2[first2, k) has copied to the result
        // [0, last3) is the merge result
        for (ptrdiff_t k = first2; k < last2 ; ++k) {
            nums1[last3++] = nums2[k];
        }
        // post condition: nums2[first2, last2) has copied to the result
    }

    if (first2 == last2) {
        // we should copy [first1, last1) to the result

        // loop invariant: k, last3
        // [first1, k) has copied to the result
        // [0, last3) is the merge result
        for (ptrdiff_t k = first1; k < last1 ; ++k) {
            nums1[last3++] = nums1[k];
        }
        // post condition: nums1[first1, last1) has copied to the result
    }
}
